﻿#pragma once
#include "Index.h"

class IRemoveDuplicates
{
public:
    /**
       * 删除有序数组中的重复项.
       * https://leetcode.cn/problems/remove-duplicates-from-sorted-array
       * 数组 双指针
       *
       * 给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
       * 元素的 相对顺序 应该保持 一致 。
       * 不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
       */
    virtual int removeDuplicates(std::vector<int>& nums) = 0;
};

class IRemoveSpecifiedValue
{
public:
    /**
     * 移除元素.
     * https://leetcode.cn/problems/remove-element/
     * 数组 双指针
     *
     * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
     * 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
     * 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
     */
    virtual int removeElement(std::vector<int>& nums, int val) = 0;
};

class RemoveArrayElements
{
public:
    
    class RemoveDuplicate:public IRemoveDuplicates
    {
    public:
        /**
		 * 快慢指针
		 * 时间:O(n) 空间:O(1)
		 */
        int removeDuplicates(std::vector<int>& nums) override
        {
            if (nums.empty())
                return 0;

            const int numsSize = nums.size();
            int accept = 0;
            for (int i = 1; i < numsSize; ++i)
            {
                if (nums[i] != nums[accept])
                    std::swap(nums[i], nums[++accept]);
            }

            return accept + 1;
        }
    };

    class RemoveValue:public IRemoveSpecifiedValue
    {
    public:
        /**
		 * 快慢指针
		 * 时间:O(n) 空间:O(1)
		 */
        int removeElement(std::vector<int>& nums, int val) override
        {
            if(nums.empty())
				return 0;
            const int numsSize = nums.size();

        	int accept = -1;
            for(int i=0;i<numsSize;++i)
            {
	            if(nums[i]!=val)
                    std::swap(nums[i], nums[++accept]);
            }

            return accept + 1;
        }
    };
};


#ifdef DEV_TEST
#include <gtest/gtest.h>
TEST(RemoveArrayElementsTest, removeDuplicates)
{
    TEST_SOLUTION1(IRemoveDuplicates,RemoveArrayElements::RemoveDuplicate)
    {
        std::vector<int> nums = TestingUtil::randRangeInts(1000, 0, 1000, 0.3f);
        std::sort(nums.begin(), nums.end());

        std::vector<int> uniqueNums;
        uniqueNums.push_back(nums.front());
        for (int i = 1; i < nums.size(); ++i)
        {
            if (nums[i] != uniqueNums.back())
                uniqueNums.push_back(nums[i]);
        }

        const int ansLen = solution->removeDuplicates(nums);
        const std::string ansNums= FormatedUtil::dumpFormated(nums.begin(), nums.begin() + ansLen);
        const std::string expectNums = FormatedUtil::dumpFormated(uniqueNums);

        ASSERT_EQ(ansLen, uniqueNums.size());
        ASSERT_EQ(ansNums, expectNums);
    };
}

TEST(RemoveArrayElementsTest,removeValue)
{
    TEST_SOLUTION1(IRemoveSpecifiedValue, RemoveArrayElements::RemoveValue,&)
    {
        //__slnTestor.TestTimes(100);

        std::vector<int> nums = TestingUtil::randRangeInts(1000, 0, 1000, 0.3f);
        const auto removeVal = TestingUtil::randIntBetween(0, 1500);
        std::vector<int> removedNums;

        for (int i = 0; i < nums.size(); ++i)
        {
            if (nums[i] != removeVal)
                removedNums.push_back(nums[i]);
        }

        const auto inputNums = FormatedUtil::dumpFormated(nums);
        const int ansLen = solution->removeElement(nums,removeVal);
        const std::string ansNums = FormatedUtil::dumpFormated(nums.begin(), nums.begin() + ansLen);
        const std::string expectNums = FormatedUtil::dumpFormated(removedNums);

    	EXPECT_EQ(ansLen, removedNums.size());
        EXPECT_EQ(ansNums, expectNums);

        if(HasFailure())
        {
            std::cout << "-----FailureContext-----" << std::endl
                << "InputNums=" << inputNums << std::endl
                << "RemoveVal=" << removeVal << std::endl;
        }
    };
}
#endif